package com.zjb.datastructure;

import com.sun.javafx.binding.StringFormatter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Dync2 {
        private int[] nums = new int[]{2,9,3,7};
        private int n = nums.length;
        private int maxLen = 0;

        /**
         *
         * @param i
         *          当前处理的元素下标
         * @param lastIdx
         *          最后一个进入到最长递增子序列的元素下标，用于比较
         */
        private void f(int i,int lastIdx,int len){
            if(i==n){
                System.out.println(String.format("结果 ：maxLen = %d， len= %d",maxLen,len));
                maxLen = Math.max(maxLen,len);
                return;
            }
            if(lastIdx == -1 || nums[i]>nums[lastIdx]){
                //加入到最长递增子数组中
                System.out.println(String.format("获得 %d，开始执行的 i = %d， lastIdx= %d , len= %d",nums[i],i+1,i,len+1));
                f(i+1,i,len+1);
            }
            //不加入到最长递增子数组中
            System.out.println(String.format("丢弃 %d ,开始执行的 i = %d， lastIdx= %d , len= %d",nums[i],i+1,lastIdx,len));
             f(i+1,lastIdx,len);
        }

        private int maxIncreaseArrayLength(){

            f(0,-1,0);
            return maxLen;
        }

    private void dync(int i,int lastIdx,int len){
        if(i==n){
            System.out.println(String.format("结果 ：maxLen = %d， len= %d",maxLen,len));
            maxLen = Math.max(maxLen,len);
            return;
        }
        if(lastIdx == -1 || nums[i]>nums[lastIdx]){
            //加入到最长递增子数组中
            System.out.println(String.format("获得 %d，开始执行的 i = %d， lastIdx= %d , len= %d",nums[i],i+1,i,len+1));
            f(i+1,i,len+1);
        }
        //不加入到最长递增子数组中
        System.out.println(String.format("丢弃 %d ,开始执行的 i = %d， lastIdx= %d , len= %d",nums[i],i+1,lastIdx,len));
        f(i+1,lastIdx,len);
        //Math.max();

    }

    public static void main(String[] args) {
        Dync2 dync2 = new Dync2();
        System.out.println(dync2.maxIncreaseArrayLength());

    }

}
